#include <stdbool.h>
#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#include "hash.h"
#include "vector_hash.h"
#include "lista.h"
#include "utils.h"

#define HASHSIZE_INICIAL 1001

/********************************************************************
*                             Prototipos
*********************************************************************/

typedef struct hash_elemento hash_elemento_t;
bool hash_redimensionar(hash_t *,size_t);
char *strdup(const char*);


/********************************************************************
*                             Implementacion
*********************************************************************/

struct hash{
    size_t cantidad;
    vector_t *vector;
    hash_destruir_dato_t destruir_dato;
};

struct hash_iter{
	vector_t *vector;
	lista_iter_t *iter_lista_actual;
	lista_t *lista_actual;
	unsigned posicion;
};

struct hash_elemento{
        char *clave;
        void *valor;
};

/* hash: form hash value for string s */
unsigned hashear(const char *s, size_t hashsize)
{
    unsigned hashval;
    for (hashval = 0; *s != '\0'; s++)
        hashval = *s + 31 * hashval;

    return hashval % hashsize;
}

hash_elemento_t *elemento_crear(const char *clave, void *dato)
{
    char *p = strdup(clave);
    if(!p)
        return NULL;

    // Pido memoria para un nuevo elemento
    hash_elemento_t *elemento = malloc(sizeof(hash_elemento_t));
    if(!elemento)
    {
        free(p);
        return NULL;
    }

    // Guardo la clave y el dato en el elemento
    elemento->clave = p;
    elemento->valor = dato;

    return elemento;
}

void elemento_destruir(void *elemento)
{
    free(((hash_elemento_t *)elemento)->clave);
    free(elemento);
}

hash_t *_crear(hash_destruir_dato_t destruir_dato,size_t hashsize)
{
    hash_t *hash = malloc(sizeof(hash_t));
    if(!hash)
        return NULL;

    vector_t *vec = vector_crear(hashsize);
    if(!vec)
    {
        free(hash);
        return NULL;
    }

    hash->cantidad = 0;
    hash->vector = vec;
    hash->destruir_dato = destruir_dato;

    return hash;
}

hash_t *hash_crear(hash_destruir_dato_t destruir_dato)
{
    return _crear(destruir_dato, HASHSIZE_INICIAL);
}

void evaluar_factor_carga(hash_t *hash)
{
    size_t n = vector_obtener_tamanio(hash->vector);

    // fc = cantidad_elementos / tamaño_tabla
    float fc = (float)(hash->cantidad)/n;

    // Si tengo una media > a 4 elementos por lista
    // redimensiono agrandando
    if(fc > 4)
    {
        if(!hash_redimensionar(hash,n*4))
            fprintf(stderr, "ERROR: hash_redimensionar devuelve false\n");

        return;
    }

    // Si tengo 1 elemento cada 8 posiciones
    // y ya agrandé
    // redimensiono achicando
    if((fc < 0.125) && (n > HASHSIZE_INICIAL))
    {
        if(!hash_redimensionar(hash,n/2))
            fprintf(stderr, "ERROR: hash_redimensionar devuelve false\n");

        return;
    }
}

bool _guardar(hash_t *hash, const char *clave, void *dato, bool considerar_fc)
{
    hash_elemento_t *elemento = elemento_crear(clave,dato);
    if(!elemento)
        return false;

    // "hasheo" la clave
    unsigned pos = hashear(clave,vector_obtener_tamanio(hash->vector));

    lista_t *lista = NULL;

    // Veo que hay en "pos"
    if(!vector_obtener(hash->vector,pos,(void *)&lista))
    {
        elemento_destruir((void *)elemento);
        return false;
    }

    bool crear_nueva_lista = (!lista);

    // Pregunto si tengo que crear una nueva lista
    if(crear_nueva_lista)
    {
        lista = lista_crear();
        if(!lista)
        {
            // Fallo crear nueva lista
            elemento_destruir((void *)elemento);
            return false;
        }
    }
    else
    {
        // Si la lista existe
        // evaluo si tengo que actualizar
        // el valor de una clave ya guardada

        // Me creo un iterador de listas
        lista_iter_t *iter = lista_iter_crear(lista);
        if(!iter)
        {
            // Fallo el iter_crear
            elemento_destruir((void *)elemento);
            return false;
        }

        while(!lista_iter_al_final(iter))
        {
            hash_elemento_t *e = lista_iter_ver_actual(iter);

            // Evaluo las claves de los "e"
            if(!strcmp(clave,((hash_elemento_t *)e)->clave))
            {
                // Tengo que actualizar

                // Borro el elemento de la lista
                lista_borrar(lista, iter);

                // Elimino el valor
                if(hash->destruir_dato)
                    hash->destruir_dato(e->valor);

                // Elimino el elemento
                elemento_destruir(e);

                // Agrego el nuevo elemento
                if(!lista_insertar_primero(lista,(void *)elemento))
                {
                    // Fallo el insertar
                    lista_iter_destruir(iter);
                    elemento_destruir((void *)elemento);
                    return false;
                }

                lista_iter_destruir(iter);

                // La cantidad no se modifica
                // Tampoco el fc
                return true;
            }

            // Si no es, avanzo...
            if(!lista_iter_avanzar(iter))
            {
                // Fallo el avanzar
                lista_iter_destruir(iter);
                elemento_destruir((void *)elemento);
                return false;
            }

        }

        // Destruyo el iterador
        lista_iter_destruir(iter);

    } // FIN: Pregunto si tengo que crear una nueva lista

    // Inserto el elemento en la lista
    if(!lista_insertar_primero(lista,(void *)elemento))
    {
        // Fallo el insertar
        if(crear_nueva_lista)
            lista_destruir(lista,NULL);

        elemento_destruir((void *)elemento);
        return false;
    }

    // Guardo la lista en el vector
    if(!vector_guardar(hash->vector,pos,(void *)lista))
    {
        // Fallo el guardar
        if(crear_nueva_lista)
            lista_destruir(lista,NULL);

        elemento_destruir((void *)elemento);
        return false;
    }

    // Incremento cantidad
    hash->cantidad++;

    // Evaluo el factor de carga
    if(considerar_fc)
        evaluar_factor_carga(hash);

    return true;
}

bool hash_guardar(hash_t *hash, const char *clave, void *dato)
{
    bool considerar_fc = true;

    return _guardar(hash,clave,dato,considerar_fc);
}

hash_elemento_t *_borrar(hash_t *hash, hash_iter_t *iter)
{
    if(hash_iter_al_final(iter))
        return NULL;

    const char *clave = hash_iter_ver_actual(iter);

    if(!clave)
    {
        fprintf(stderr, "ERROR: hash_iter_ver_actual devuelve NULL\n");
        return NULL;
    }

    // Dejo a iter en una pos válida
    if(!hash_iter_avanzar(iter))
    {
        fprintf(stderr, "ERROR: iter avanzar devolvió false\n");
        return NULL;
    }

    void *dato = hash_obtener(hash, clave);
    if(!dato)
    {
        fprintf(stderr, "ERROR: hash_obtner devuelve false\n");
        return NULL;
    }

    hash_elemento_t *e = elemento_crear(clave,dato);

    if(!e)
    {
        fprintf(stderr, "ERROR: elemento_crear devuelve NULL\n");
        return NULL;
    }

    hash_borrar(hash,clave);

    return e;
}

bool hash_redimensionar(hash_t *hash, size_t tamanio_nuevo)
{
    // Creo un hash auxiliar
    hash_t *aux = _crear(hash->destruir_dato,tamanio_nuevo);
    if(!aux)
        return false;

    // Creo un iter sobre el hash
    hash_iter_t *iter = hash_iter_crear(hash);
    if(!iter)
    {
        // Fallo el iter_crear
        hash_destruir(aux);
        return false;
    }

    // Itero el hash
    while(!hash_iter_al_final(iter))
    {
        // Obtengo el elemento y lo borro del hash
        hash_elemento_t *e = _borrar(hash,iter);

        if(!e)
        {
            fprintf(stderr, "ERROR: _borrar devuelve NULL\n");
            hash_destruir(aux);
            hash_iter_destruir(iter);
            return false;
        }

        // Guardo clave-dato
        bool considerar_fc = false;
        if(!_guardar(aux,e->clave,e->valor,considerar_fc))
        {
            // Fallo el guardar
            fprintf(stderr, "ERROR: _guardar devuelve false\n");
            elemento_destruir(e);
            hash_destruir(aux);
            hash_iter_destruir(iter);
            return false;
        }

        elemento_destruir(e);

        // Avanzo el iter
        // el _borrar deja el iter en una pos válida o al final
    }

    hash_iter_destruir(iter);

    // Swapp de vectores
    vector_t *v = hash->vector;

    hash->vector = aux->vector;

    aux->vector = v;

    // Swapp de cantidad
    hash->cantidad = aux->cantidad;

    // Destruyo el hash auxiliar
    hash_destruir(aux);

    return true;
}

void *hash_borrar(hash_t *hash, const char *clave)
{
    lista_t *lista = NULL;

    void *valor = NULL;

    // hasheo la clave
    unsigned pos = hashear(clave, vector_obtener_tamanio(hash->vector));

    // Obtengo lo que hay en pos
    if(!vector_obtener(hash->vector,pos,(void *)(&lista)))
        return NULL;

    if(!lista)
        return NULL;

    lista_iter_t *iter = lista_iter_crear(lista);
    if(!iter)
        return NULL;

    hash_elemento_t *e = NULL;

    // Recorro la lista
    while(!lista_iter_al_final(iter))
    {
        e = lista_iter_ver_actual(iter);

        // Evaluo la clave
        if(!strcmp(clave,e->clave))
        {
            // Clave encontrada
            valor = e->valor;

            lista_borrar(lista,iter);

            // Si la lista esta vacia
            // la destruyo
            if(lista_esta_vacia(lista))
            {
                lista_destruir(lista,NULL);

                // Cargo NULL en pos del vector
                if(!vector_guardar(hash->vector,pos,NULL))
                {
                    // Fallo el guardar
                    lista_iter_destruir(iter);
                    return NULL;
                }
            }

            // Elimino el elemento
            elemento_destruir((void *)e);

            lista_iter_destruir(iter);

            // Decremento cantidad
            hash->cantidad--;

            return valor;
        }

        // Si no es avanzo...
        if(!lista_iter_avanzar(iter))
        {
            // Fallo el avanzar
            lista_iter_destruir(iter);
            return NULL;
        }
    }

    lista_iter_destruir(iter);

    // Clave no encontrada
    return valor;
}

void *hash_obtener(const hash_t *hash, const char *clave)
{
    // hasheo la clave
    unsigned pos = hashear(clave,vector_obtener_tamanio(hash->vector));

    // Obtengo la lista de pos
    lista_t *lista;
    if(!vector_obtener(hash->vector,pos,(void *)(&lista)))
        return NULL;

    if(!lista)
        return NULL;

    // Recorrer la lista
    hash_elemento_t *elemento;

    lista_iter_t *iter = lista_iter_crear(lista);
    if(!iter)
        return NULL;

    while(!lista_iter_al_final(iter))
    {
        elemento = lista_iter_ver_actual(iter);

        // Evaluo la clave
        if(!strcmp(clave,((hash_elemento_t *)elemento)->clave))
        {
            // Clave encontrada
            lista_iter_destruir(iter);
            return ((hash_elemento_t *)elemento)->valor;
        }

        // Si no es avanzo...
        if(!lista_iter_avanzar(iter))
        {
            // Fallo el avanzar
            lista_iter_destruir(iter);
            return NULL;
        }
    }

    lista_iter_destruir(iter);

    // Clave no encontrada
    return NULL;
}

bool hash_pertenece(const hash_t *hash, const char *clave)
{
    // hasheo la clave
    unsigned pos = hashear(clave,vector_obtener_tamanio(hash->vector));

    lista_t *lista = NULL;

    // Obtengo lo que hay en pos
    if(!vector_obtener(hash->vector,pos,(void *)(&lista)))
        return false;

    if(!lista)
        return false;

    lista_iter_t *iter = lista_iter_crear(lista);
    if(!iter)
        return false;

    while(!lista_iter_al_final(iter))
    {
        hash_elemento_t *e = lista_iter_ver_actual(iter);

        // Evaluo las claves de los e's
        if(!strcmp(clave,((hash_elemento_t *)e)->clave))
        {
            // Clave encontrada
            lista_iter_destruir(iter);
            return true;
        }

        // Si no es, avanzo...
        if(!lista_iter_avanzar(iter))
        {
            // Fallo el avanzar
            lista_iter_destruir(iter);
            return false;
        }
    }

    // Destruyo el iterador
    lista_iter_destruir(iter);

    // No pertenece
    return false;
}

size_t hash_cantidad(const hash_t *hash)
{
    return hash->cantidad;
}

void hash_destruir(hash_t *hash)
{
    size_t n = vector_obtener_tamanio(hash->vector);

    lista_t *lista = NULL;

    for(unsigned i=0; i<n; i++)
    {

        if(!vector_obtener(hash->vector,i,(void *)(&lista)))
        {
            // Fallo el obtener
            break;
        }

        if(!lista)
        continue;

        while(!lista_esta_vacia(lista))
        {
            hash_elemento_t *e = lista_borrar_primero(lista);
            if(hash->destruir_dato)
                hash->destruir_dato(e->valor);

            elemento_destruir(e);
        }

        lista_destruir(lista, NULL);
    }

    vector_destruir(hash->vector);
    free(hash);
}

/////////////////////////////////////////////////////////////////////////
lista_t *buscar_siguiente_lista_no_nula_ni_vacia(vector_t *vector,unsigned *i)
{
	lista_t	*lista = NULL;

	size_t n = vector_obtener_tamanio(vector);

	do
	{
		// Obtengo la lista de la posicion i
		if(!vector_obtener(vector,*i,(void*)(&lista)))
		{
            // Fallo el obtener
            return NULL;
		}

		if((lista) && (!lista_esta_vacia(lista)))
            return lista;

		(*i)++;

	}while(n > *i);

	return lista;
}

hash_iter_t *hash_iter_crear(const hash_t *hash)
{
	hash_iter_t *hash_iter = malloc(sizeof(hash_iter_t));

	if(!hash_iter)
 		return NULL;

	hash_iter->vector = hash->vector;

	hash_iter->posicion = 0;

    lista_t* lista = NULL;

	// Paso la posicion del iterador,
	// para que quede igualada a la posicion de la primer
	// lista no vacia del vector
	lista = buscar_siguiente_lista_no_nula_ni_vacia(hash->vector,&(hash_iter->posicion));


	hash_iter->lista_actual = lista;

    hash_iter->iter_lista_actual = NULL;

    // Creo un iterador sobre la lista de la posicion "hash_iter->posicion"
	if(lista)
	{
	    hash_iter->iter_lista_actual = lista_iter_crear(lista);

	    // Controlo que no fallo
	    if(!hash_iter->iter_lista_actual)
	    {
	        free(hash_iter);
	        return NULL;
	    }
	}

	return hash_iter;
}

bool hash_iter_avanzar(hash_iter_t *iter)
{
	if(!iter->iter_lista_actual)
        return false;

	// Si no estoy al final de la lista, avanzo
	if(!lista_iter_al_final(iter->iter_lista_actual))
	{
	    if(!lista_iter_avanzar(iter->iter_lista_actual))
            return false;

        // Si luego de avanzar, estoy al final
        // busco la práxima lista
        if(!lista_iter_al_final(iter->iter_lista_actual))
            return true;
	}

    // Si estoy al final de la lista
    // libero el iterador
    lista_iter_destruir(iter->iter_lista_actual);

    iter->iter_lista_actual = NULL;

    // Incremento la pos
    iter->posicion +=1;

    // Busco la proxima lista
    lista_t *lista = buscar_siguiente_lista_no_nula_ni_vacia(iter->vector,&(iter->posicion));

    // TODO: borrar
    iter->lista_actual = lista;

    // Si no se encontro una lista siguiente
    // termino y estoy al final
    // ?
    if(!lista)
        return true;

    // Creo un nuevo iterador sobre la lista nuevo
    iter->iter_lista_actual = lista_iter_crear(lista);

    if(!iter->iter_lista_actual)
    {
        // Fallo el iter_lista crear
        puts(" => SALIDA 1: error creando el nuevo iterador de lista");
        return false;
    }

    return true;
}

const char *hash_iter_ver_actual(const hash_iter_t *iter)
{
    if(hash_iter_al_final(iter))
        return NULL;

    hash_elemento_t *e = lista_iter_ver_actual(iter->iter_lista_actual);

    return e->clave;
}

bool hash_iter_al_final(const hash_iter_t *iter)
{
	if(!iter->iter_lista_actual)
        return true;

    return lista_iter_al_final(iter->iter_lista_actual);
}

void hash_iter_destruir(hash_iter_t* iter)
{
    //Libera la memoria del iterador de listas
    lista_iter_destruir(iter->iter_lista_actual);
	//Libera la memoria propia del iterador del hash
	free(iter);
}
